1. Field of the Invention
The present invention generally relates to the art of microelectronic integrated circuit layout, and more specifically to the art of placement of cells on integrated circuit chips.
2. Description of Related Art
Microelectronic integrated circuits consist of a large number of electronic components which are fabricated by layering several different materials on a silicon base or wafer. The design of an integrated circuit transforms a circuit description into a geometric description which is known as a layout. A layout consists of a set of planar geometric shapes in the various layers of the silicon chip.
The process of converting the specifications of an electrical circuit into a layout is called physical design. Physical design requires arranging elements, wires, and predefined cells on a fixed area, and the process can be tedious, time consuming, and prone to many errors due to tight tolerance requirements and the minuteness of the individual components, or cells.
Currently, the minimum geometric feature size of a component is on the order of 0.5 microns. Feature size may be reduced to 0.1 micron within the next several years. The current small feature size allows fabrication of as many as 10 million transistors or approximately 1 million gates of logic on a 25 millimeter by 25 millimeter chip. This feature-size-decrease/transistor-increase trend is expected to continue, with even smaller feature geometries and more circuit elements on an integrated circuit. Larger chip sizes will allow far greater numbers of circuit elements.
Due to the large number of components and the exacting details required by the fabrication process, physical design is not practical without the aid of computers. As a result, most phases of physical design use extensively Computer Aided Design (CAD) tools. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance.
The object of physical chip design is to determine an optimal arrangement of devices in a plane and to find an efficient interconnection or routing scheme between the devices that results in the desired functionality. Since space on the chip surface is at a premium, algorithms must use the space very efficiently to lower costs and improve yield. The arrangement of individual cells in an integrated circuit chip is known as a cell placement.
Each microelectronic circuit device or cell includes a plurality of pins or terminals, each of which is connected to pins of other cells by a respective electrical interconnection wire network, or net. A purpose of the optimization process used in the physical design stage is to determine a cell placement such that all of the required interconnections can be made, but total wirelength and interconnection congestion are minimized.
Typical methods for achieving this goal include generating one or more initial placements and modifying the placement or placements using optimization methodologies such as simulated annealing, genetic algorithms (i.e. simulated evolution), and force directed placement. Each of these techniques involve iterative applications of the respective algorithms to arrive at an estimate of the optimal arrangement of the cells.
Depending on the input, placement algorithms are classified into two major groups, constructive placement algorithms and iterative improvement algorithms. The input to the constructive placement algorithms consists of a set of blocks along with the netlist. The algorithm provides locations for the blocks. Iterative improvement algorithms start with an initial placement. These algorithms modify the initial placement in search of a better placement. The algorithms are applied in a recursive or an iterative manner until no further improvement is possible, or the solution is considered to be satisfactory based on certain predetermined criteria.
Iterative placement algorithms can be divided into three general classifications: simulated annealing, simulated evolution and force directed placement. The simulated annealing algorithm simulates the annealing process that is used to temper metals. Simulated evolution simulates the biological process of evolution, while the force directed placement simulates a system of bodies attached by springs.
Assuming that a number N of cells are to be optimally arranged and routed on an integrated circuit chip, the number of different ways that the cells can be arranged on the chip, or the number of permutations, is equal to N| (N factorial). In the following description, each arrangement of cells will be referred to as a placement. In a practical integrated circuit chip, the number of cells can be hundreds of thousands or millions. Thus, the number of possible placements is extremely large.
Because of the large number of possible placements, computerized implementation of the placement algorithms discussed above can take many days. In addition, the placement algorithm may need to be repeated with different parameters or different initial arrangements to improve the results.
Iterative algorithms function by generating large numbers of possible placements and comparing them in accordance with some criteria which is generally referred to as fitness. The fitness of a placement can be measured in a number of different ways, for example, overall chip size. A small size is associated with a high fitness and a large size is associated with a low fitness. Another measure of fitness is the total wire length of the integrated circuit. A high total wire length indicates low fitness and a low total wire length, on the other hand, indicates high fitness. One cell placement optimization system is described in U.S. patent application Ser. No. 08/672,725. Applicants hereby incorporate the specification, including the drawings, of said application herein as though set forth in full.
The relative desirability of various placement configurations can alternatively be expressed in terms of cost, which can be considered as the inverse of fitness, with high cost corresponding to low fitness and, similarly, low cost corresponding to high fitness.
The cost or the desirability of various placement configuration can be measured using other methods such as capacity distribution and utilization ratio. Capacity distribution and utilization ratios measure the placement of the cells for each of the functional blocks for the integrated circuit. An integrated circuit is designed with various functional blocks, or functions, which, operating together, achieves the desired operation. Each of the functions of the circuit is implemented by a plurality of cells and is assigned a portion of the core space upon which the cells are placed. For example, an integrated circuit design may require the use of a central processor unit (CPU) function, memory function, and some type of input/output (I/O) function.
In this document, the terms and phrases "core," "core space," "core area," "floor," "floor space," and "integrated circuit," will be used interchangeably to refer to the area of the integrated circuit upon which cells are placed to implement various functions of the integrated circuit.
The capacity is the maximum amount of cells which can be placed on the core space or any portion of the core space and is usually measured in cell height units. Provided that entire core space has sufficient capacity, it is often desirable to place the cells on the core space with a certain capacity distribution. For instance, it may be desirable that the cells of the integrated circuit be distributed evenly throughout the chip to avoid high concentration of the cells in a small location with a low concentration of the cells for the rest of the core space. On the other hand, it may be desirable to implement certain functions of the chip on a small portion of the core space with a high concentration of the cells. In sum, a predetermined capacity distribution of the core space or for any function assigned to a portion of the core space may be one of the requirements of the cell placement.
A closely related concept is the utilization of the space. The utilization is the ratio of the amount of the actual core space use within a predefined portion of the core space to the capacity of the core space for the predefined portion of the core space. For example, if a portion of the core space assigned to a function has a capacity of 100,000 cell height units, and the cells to implement the function uses 50,000 cell height units, then the utilization of the portion of the core space is 50 percent.
The capacity distribution or the utilization ratio for each of the functions of the integrated circuit or for the entire core space may be predetermined as an engineering parameter based on such factors as heat dissipation, power management, manufacturing constraints, etc.
An exemplary integrated circuit chip is illustrated in FIG. 1 and generally designated by the reference numeral 10. The circuit 10 includes a semiconductor substrate 10A on which are formed a number of functional circuit blocks that can have different sizes and shapes.
As illustrated by FIG. 1, the functions such as the central processing unit (CPU) 12, Read Only Memory (ROM) 14 and the others are assigned portions of the integrated chip 10. Some functions are assigned to a relatively large portion of the core space. These are the CPU 12, the ROM, (ROM) 14, a clock/timing unit 16, one or more random access memories (RAM) 18 and an input/output (I/O) interface unit 20.
The integrated circuit 10 further comprises a large number of small cells 22 which can number tens of thousands, hundreds of thousands, or even millions or more. These cells 22 may implement various functions of the integrated circuit. For example, a group of cells of a sub-area 28 may represent an implementation of a function to prepare data for the I/O function 20.
Although not visible in the drawing, the various elements of the circuit 10 are interconnected by electrically conductive lines or traces that are routed, for example, through vertical channels 24 and horizontal channels 26 that run between the cells 22.
The current methods of optimally placing the cells on the integrated circuit involve (1) assigning functions to be implemented to portions of the integrated circuit; (2) placing the cells of each of the functions onto the assigned portion of the integrated circuit using a placement algorithm; (3) calculating the capacity distribution of the integrated circuit and the utilization rate of each portion of the integrated circuit used to implement its function; and (4) iterating the first three steps to obtain a better placement in terms of capacity distribution or utilization.
The disadvantages of the current process involve time and accuracy. Because the placement process requires manual iteration between floor planing tools (to calculate and evaluate capacity and utilization) and placement tools (to newly place the cells onto the core), the optimal placement process takes a long time. Also, is difficult to manually optimize many different parameters simultaneously because, at each iteration, the operator has to simultaneously consider many parameters--overall capacity, capacity distribution, overall utilization, utilization of each functions, utilization distribution, overlap size among functions, aspect ratio of functions, etc. Even with highly experience professionals, the simultaneous consideration of all of the parameters for an optimal cell placement is an extremely difficult process. Further, the complexity of the cell placement process is continually increasing as the number of functions and the number of cells on integrated chips increase, rendering manual analysis techniques to become nearly impossible to perform.
In summary, because of the ever-increasing complexity of integrated circuit chips and the number of cells required to implement the functions of the complex designs, the manual placement optimization methods are fast becoming obsolete. The manual floor planning and cell placement optimization process requires an inordinate amount of time because the process requires manual iteration between running floor plan tools and placement tools. In additional, it is extremely difficult, at best, for human beings to simultaneously optimize several parameters (function utilization, overlap size among functions, aspect ratios of functions, etc.).